package gold.digger;

import gold.utils.InputUtil;
import gold.vo.CodeDoc;

import java.util.Arrays;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC329 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        public int longestIncreasingPath(int[][] matrix) {
            if (matrix.length == 0) {
                return 0;
            }

            //visited有两个作用：1.判断是否访问过，2.存储当前格子的最长递增长度
            int[][] visited = new int[matrix.length][matrix[0].length];
            int max = 0;
            //遍历------将每个数的最大增长长度遍历出来，然后筛选出最大的
            for (int i = 0; i < matrix.length; i++) {
                for (int j = 0; j < matrix[0].length; j++) {
                    if (visited[i][j] == 0) {
                        //这里先做一次比较找出max，可以避免最后再去遍历一个visited数组
                        max = Math.max(max, dfs(i, j, matrix, visited));
                    }
                }
            }
            return max;
        }

        public int dfs(int i, int j, int[][] matrix, int[][] visited) {
            if (i < 0 || i >= matrix.length || j < 0 || j >= matrix[0].length) {
                //这里是对递归回来的数的判定
                return 0;
            }

            if (visited[i][j] > 0) {
                //该数已经存储了最大增长长度，直接返回
                return visited[i][j];
            }

            int max = 0;
            //这里分别去判断4周是否比当前数小，然后去递归遍历
            //直到遍历出当前值的四周比它小的数当中的最大的连续增长值
            //然后连续增长值+1就是当中数的连续增长
            //递归过程当中得到的数的连续增长值，存储在visited数值当中
            if (i - 1 >= 0 && matrix[i - 1][j] < matrix[i][j]) {
                max = Math.max(max, dfs(i - 1, j, matrix, visited));
                //左边
            }
            if (i + 1 < matrix.length && matrix[i + 1][j] < matrix[i][j]) {
                max = Math.max(max, dfs(i + 1, j, matrix, visited));
                // 右边
            }
            if (j - 1 >= 0 && matrix[i][j - 1] < matrix[i][j]) {
                max = Math.max(max, dfs(i, j - 1, matrix, visited));
                //下边
            }
            if (j + 1 < matrix[0].length && matrix[i][j + 1] < matrix[i][j]) {
                max = Math.max(max, dfs(i, j + 1, matrix, visited));
                //上边
            }

            visited[i][j] = max + 1;//得到的最大的增长长度加一就是当前数的最大增长度
            //存储该数的最大增长长度
            return max + 1;

        }
    }


    /**
     * 该方法没有逻辑问题，但是因为重复计算结果未保存到visited数组中，导致搜索复杂度为2^(m*n)
     * 对于本次的测试用例，2的100次方的计算量，果然得不出结果。。。
     */
    class SolutionFail {
        public int longestIncreasingPath(int[][] arr) {
            if (null == arr || arr.length <= 0) return 0;

            int maxLength = Integer.MIN_VALUE;
            int[][] visited = new int[arr.length][arr[0].length];
            for (int i = 0; i < arr.length; i++) {
                for (int j = 0; j < arr[0].length; j++) {
                    if (visited[i][j] == 0) {
                        int curPath = DFSSerach(arr, visited, i, j, i, j);
                        if (maxLength < curPath) maxLength = curPath;
                    }
                }
            }

            return maxLength;
        }

        public int DFSSerach(int[][] arr, int[][] visited, int x, int y, int i, int j) {
            if (i < 0 || i > visited.length - 1 || j < 0 || j > visited[0].length - 1 || (!(x == i && y == j) && arr[x][y] >= arr[i][j])) {
                return 0;
            }

            if (visited[i][j] > 0) {
                //该数已经存储了最大增长长度，直接返回
                return visited[i][j];
            }

            int curMaxLength = 1;//current i,j give a length 1.
            curMaxLength = Math.max(curMaxLength, DFSSerach(arr, visited, i, j, i, j - 1) + 1);
            curMaxLength = Math.max(curMaxLength, DFSSerach(arr, visited, i, j, i, j + 1) + 1);
            curMaxLength = Math.max(curMaxLength, DFSSerach(arr, visited, i, j, i - 1, j) + 1);
            curMaxLength = Math.max(curMaxLength, DFSSerach(arr, visited, i, j, i + 1, j) + 1);

            visited[i][j] = curMaxLength;
            return curMaxLength;
        }
    }


    public void run() {
        SolutionFail solution = new SolutionFail();
        int[][] arr = InputUtil.toDoubleIntegerArray("[[0,1,2,3,4,5,6,7,8,9],[19,18,17,16,15,14,13,12,11,10],[20,21,22,23,24,25,26,27,28,29],[39,38,37,36,35,34,33,32,31,30],[40,41,42,43,44,45,46,47,48,49],[59,58,57,56,55,54,53,52,51,50],[60,61,62,63,64,65,66,67,68,69],[79,78,77,76,75,74,73,72,71,70],[80,81,82,83,84,85,86,87,88,89],[99,98,97,96,95,94,93,92,91,90],[100,101,102,103,104,105,106,107,108,109],[119,118,117,116,115,114,113,112,111,110],[120,121,122,123,124,125,126,127,128,129],[139,138,137,136,135,134,133,132,131,130],[0,0,0,0,0,0,0,0,0,0]]");
        System.out.println(solution.longestIncreasingPath(arr));
    }

    public static void main(String[] args) throws Exception {
        LC329 an = new LC329();
        an.run();

        Arrays.toString("".split(","));
        InputUtil.run();
        CodeDoc.run();
        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
